Sharding: Cross-shard communication

UTXO-based

Atomix (Omniledger)

Leader (same with the leader in PBFT) of each shard generate proof-of-acceptance or proof-of-rejection

https://gyazo.com/4c24a4c02a396a9ede68247b178da1d4

Unlocking is user-driven (OK because it's cryptocurrency application)

Sharded Byzantine Atomic Commit (Chainspace)

ethresear.ch

https://gyazo.com/d6426fb654e812e467c2365e6a2dd047

Nodes know whether T is commited or aborted by seeing LOCALPREPARED(commit / abort, T) signed by$ > f + 1nodes

The leader of each shard coordinates this voting

$ O(S^2)communication complexity ($ Sis the number of concerned shards per transaction)

Rapidchain's

Split a cross-shard transfer$ TX = <(I_1, I_2), O>into three single-shard transactions

$ T_1 = <I_1, I_1'>, ~T_2 = <I_2, I_2'>, ~T_3 = <(I_1', I_2'), O>, where$ I_i'belongs to the output shard

If either$ T_1or$ T_2fails, use$ I_2'or$ I_1'

No isolation (pointed out by Dang et al.)

If$ T_1fails, the whole$ TXfails. Additionally, another $ T_2'can also fail if it comes after$ T_2.

These are route through Inter-committee routing protocol, based on a routing algorithm of Kademlia

Account-based

Eth2

ETH2.0: Cross-shard Communication

2PL

Towards Scaling Blockchain Systems via Sharding (Dang et al. SIGMOD'19)

Replace the coordinator of 2PC with a reference committee

Implemented as a chaincode of Hyperledger fabric

Running multiple instances of reference committees in parallel to scale it out

nrryuya.icon > Why does they claim "isolation"?

Others

Solving Train-And-Hotel Problem with Asynchronous Message (and await/async) @ethresear.ch

Canceling-based sheme for atomic cross-shard transaction, making a free-option problem

you could limit free-option issues by having a system where there is a 1-minute cancellation period, but that introduces a safety risk as what if the blockchain or the user’s access to the blockchain doesn’t work for 1 minute because of internet issues; atomicity could break

Replay protection

Eth2

See ETH2.0: Cross-shard Communication

Byzcuit

Replay Attacks and Defenses Against Cross-shard Consensus in Sharded Distributed Ledgers

Alberto Sonnino, Shehar Bano, Mustafa Al-Bassam, George Danezis (University College London)

Replay attacks against 2 phase commit based X-shard schemes (Chainspace, Omniledger and also on Ethereum's yanking in Appendix A)

They allow an attacker, with network access only, to double spend or lock resources with minimal efforts.

Present Byzcuit: 2PC-based X-shard schemes, which does not require storing growing permanent state

OTOH, mutex-based schemes (like Eth2's yanking) require min 1 byte/tx of permanent storage or trade-offs

Video @Simons Institute

Cross-chain Protocols